/**
 * 哈夫曼树的构建
 */

#include<stdio.h>
#include<stdlib.h>
typedef struct HNODE
{
    int weight;
    struct HNODE *left,*right;
}HTree;
//在oiwiki里面的实例代码，写的是*Htree这样写，后续不带*的Htree都默认是指针
//这里为了自己理解，没有写*，那么后面的指针都需要手动写*

HTree *tree;//哈夫曼树，根节点

#define N 1000

HTree* createHuffmanTree(int array[],int n){
    HTree* forest[N];//存储森林，实际上就是树的数组
    HTree* root=NULL;
    //初始化森林，现在森林中的每个树都只有根节点，并且weight就是对应数组里面的值
    for(int i=0;i<n;i++){
        HTree* temp;
        temp=(HTree*) malloc (sizeof(HTree));
        temp->weight=array[i];
        temp->left=temp->right=NULL;
        forest[i]=temp;
    }
    //从第二个树开始找
    for(int i=1;i<n;i++){
        int minn=-1,minnSub;//最小值和次小值

        //下面两个for是用来找权值最小的两棵树的，他们的下标给minn和minnSub
        for(int j=0;j<n;j++){//用for循环找第一个不为空的树，因为森林中的有些节点合并之后，会删除部分节点，导致树根为空
            if(forest[j]!=NULL&&minn==-1){//只有第一次会赋值，因为第一次minn=-1成立
                minn=j;
                continue;
            }
            if(forest[j]!=NULL){//找第二个不为空的树根作为minnSub的初始值
                minnSub=j;
                break;
            }
        }
        for(int j=minnSub;j<n;j++){//不断更新minn和minSub，找到最小的两颗树
            if(forest[j]!=NULL){//不为空就一直比较
                if(forest[j]->weight < forest[minn]->weight){//找到比最小值还小的，那么此时原来的最小值就是次小值，当前的为最小值
                    minnSub=minn;
                    minn=j;
                }else if(forest[j]->weight<forest[minnSub]->weight){//找到比次小值小的，但是这个值一定比最小值大（因为上面那个循环），所以更新次小值
                    minnSub=j;
                }
            }
        }
        //建立新树
        root=(HTree*)malloc(sizeof(HTree));
        root->weight=forest[minn]->weight+forest[minnSub]->weight;//新的根节点是两个值最小节点的和
        root->left=forest[minn];//同时新节点的左右字数就是那两个节点
        root->right=forest[minnSub];

        forest[minn]=root;
        forest[minnSub]=NULL;//minSub位置为空
    }
    return root;

}


int main(void){
    int array[]={};

    return 0;
}